#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> need;
        int cnt = t.length();
        for (char c : t) {
            need[c]++;
        }
        int i = 0, j = 0, needCnt = t.length();
        tuple<int, int> res = {0, s.length()};
        for (; j<s.size(); j++) {
            if (need[s[j]] > 0) {
                needCnt--;
            }
            need[s[j]]--;
            if (needCnt == 0) {
                while (true) {
                    char c = s[i];
                    if (need[c] == 0) { break; }
                    need[s[i++]]++;
                }
                if (j - i < get<1>(res) - get<0>(res)) {
                    res = {i, j};
                }
                need[s[i++]]++;
                needCnt++;
            }
        }
        return get<1>(res) >= s.size() ? string("") : s.substr(get<0>(res), get<1>(res)-get<0>(res)+1);
    }
};


int main(void) {
    Solution soln = Solution();
    cout << soln.minWindow(string("ADOBECODEBANC"), string("ABC"));
    cout << " == " << string("BANC");
    return 0;
}
